package unplag;


import java.util.*;
import java.io.*;

class KrGstMatch {

    public static int searchLength;
    public static StringBuffer T = new StringBuffer();
    public static StringBuffer P = new StringBuffer();
    public static RkGst rs = new RkGst();
    public static ArrayList<Match> titles = new ArrayList<Match>();

    public static void main(String[] args) throws Exception {
//StringBuffer T=new StringBuffer();
        //StringBuffer P=new StringBuffer();

        FileInputStream fis1 = new FileInputStream(args[0]);
        InputStreamReader isr1 = new InputStreamReader(fis1);
        BufferedReader br1 = new BufferedReader(isr1);

        FileInputStream fis2 = new FileInputStream(args[1]);
        InputStreamReader isr2 = new InputStreamReader(fis2);
        BufferedReader br2 = new BufferedReader(isr2);



        String strLine1;
        String strLine2;

        while ((strLine1 = br1.readLine()) != null) {
            T.append(strLine1);
        }
        while ((strLine2 = br2.readLine()) != null) {
            P.append(strLine2);
        }


        int lmax, s, minmatch;
        s = 3;
        minmatch = 1;
        while (s > minmatch) {
            lmax = scanpattern(s);
            if (lmax > 2 * s) {
                s = lmax;
            } else {
                //rs.print();
                //System.out.println(s);
                markmatch(s);
                if (s > 2 * minmatch) {
                    s = (int) Math.ceil((double) s / 2);//应该是向下取整
                    //System.out.println(s);
                } else //if(s==lmax&&s>minmatch)
                if (s > minmatch) {
                    s = minmatch;
                }
            }
        }
        System.out.println(T);
        System.out.println(titles);

        System.out.println(P);
    }

    public static int scanpattern(int s) throws Exception {
        ArrayList<Hashstruct> Thashtable = new ArrayList<Hashstruct>();
        ArrayList<Hashstruct> Phashtable = new ArrayList<Hashstruct>();
        TextStructure ts = new TextStructure(T);
        Thashtable = ts.creatHashtable(s);//为文本串创建长度为s的哈希表

        TextStructure ps = new TextStructure(P);
        Phashtable = ps.creatHashtable(s);

        int hv, k, maxlen = 0, mm;
        for (int m = 0; m < Phashtable.size(); m++) {
//System.out.println(Phashtable.size());
//System.out.println(Phashtable.get(m).gethashvalue());
            hv = ts.searchhashvalue(Phashtable.get(m).gethashvalue());
//System.out.println(hv);
            if (hv != -1)//扩展匹配
            {
                k = s;
                mm = Phashtable.get(m).getposition();
//System.out.println(mm);
                if ((k + mm) < P.length() && (hv + k) < T.length()) {
                    while ((P.charAt(k + mm) != ' ') && (T.charAt(hv + k) != ' ') && (P.charAt(k + mm) == T.charAt(hv + k))) {
                        k = k + 1;
                        if ((k + mm) >= P.length() || (hv + k) >= T.length()) {
                            break;
                        }
                    }
                }
//System.out.println(k);
                if (k > 2 * s) {
                    return k;
                } else {
                    Match match = new Match(mm, hv, k);
                    rs.addMatch(match);
//System.out.println(match);
//rs.print();
//System.out.println('*');
                    if (k > maxlen) {
                        maxlen = k;
                    }
                }
            }
        }
        return maxlen;
    }

    public static void markmatch(int s) {
        ArrayList<QMatch> q = new ArrayList<QMatch>();

        int cs = rs.que.size();
        for (int j = 0; j < cs; j++)//将队列que按照匹配长度降序排序
        {
            int max = 0;
            for (int i = 0; i < rs.que.size(); i++)//找出最大值
            {
                if (rs.que.get(i).getL() > max) {
                    max = rs.que.get(i).getL();
                }
            }
            for (int k = 0; k < rs.que.size(); k++)//将最大值放在队列q中，并将其从que中移除
            {
                if (rs.que.get(k).Lque == max) {
                    q.add(rs.que.get(k));
                    rs.que.remove(rs.que.get(k));
                    break;
                }
            }
            //System.out.println(q.get(j).matches);
        }
        rs.que = q;
        for (int i = 0; i < rs.que.size(); i++) {
            LinkedList<Match> mc = rs.que.get(i).matches;
//rs.print();
            int L;
            for (int j = 0; j < mc.size(); j++) {
                L = rs.que.get(i).getL();

                Match mt = mc.get(j);
//System.out.println(j);
//System.out.println(mt);
                if (!occlued(mt)) {
                    int n, m, l;
                    n = mt.getn();
                    m = mt.getm();
                    l = mt.getl();
                    boolean b = true;
                    for (int k = 0; k < s; k++) {
                        if (P.charAt(m + k) != T.charAt(n + k)) {
                            //rs.que.get(i).matches.remove(mt);
                            b = false;
                            break;
                        }
                    }
                    if (b) {
                        mark(T, n, l);
                        mark(P, m, l);
                        //rs.que.get(i).matches.remove(mt);
                        titles.add(mt);
                    }
                }
                /*else
                rs.que.get(i).matches.remove(mt);*/
            }
        }
        rs.que.clear();
    }

    public static void mark(StringBuffer Text, int p, int l) {
        for (int i = p; i < p + l; i++) {
            Text.setCharAt(i, ' ');
        }
        //System.out.println(Text);
    }

    public static boolean occlued(Match m)//判断是否存在交叠
    {
        boolean b = false;
//System.out.println(titles);
        for (int i = 0; i < titles.size(); i++) {
            Match mt = titles.get(i);
            int m1, m2, n1, n2, l1, l2;
            m1 = mt.getm();
            m2 = m.getm();
            n1 = mt.getn();
            n2 = m.getn();
            l1 = mt.getl();
            l2 = m.getl();
            if (((m1 < m2) && (m1 + l1 > m2)) || ((m2 < m1) && (m2 + l2 > m1))) {
                b = true;
                return b;
            }
            if ((n1 < n2) && (n1 + l1 > n2) || (n2 < n1) && (n2 + l2 > n1)) {
                b = true;
                return b;
            }

        }
        return b;
    }
}

class RkGst {

    ArrayList<QMatch> que = new ArrayList<QMatch>();

    public void addMatch(Match m) {
        int Len = m.getl();
        if (que.isEmpty() == true) {
            que.add(new QMatch(Len));
            que.get(0).matches.add(m);
        } else {
            int i;
            for (i = 0; i < que.size(); i++) {
                if (que.get(i).getL() == Len) {
                    que.get(i).matches.add(m);
                    break;
                }
            }
            if (i >= que.size()) {
                que.add(new QMatch(Len));
                que.get(i).matches.add(m);
            }
        }
    }

    public Match getMatch(int L) {
        for (int i = 0; i < que.size(); i++) {
            if (que.get(i).Lque == L) {
                return que.get(i).matches.getLast();
            }
        }
        return (new Match(0, 0, 0));
    }

    public void print() {
        for (int i = 0; i < que.size(); i++) {
            System.out.println(que.get(i).matches);
//System.out.println(que.get(i).Lque);
        }
    }
}

class TextStructure {

    StringBuffer Text = new StringBuffer();
    ArrayList<Hashstruct> Hashtable = new ArrayList<Hashstruct>();
    int num;

    TextStructure(StringBuffer T) {
        this.Text = T;
    }

    public ArrayList<Hashstruct> creatHashtable(int len) {

        int sum;

        for (int i = 0; i < Text.length() - len + 1; i++) {
            sum = 0;
            while (Text.charAt(i + sum) != ' ') {
                sum = sum + 1;
                if (sum == len) {
                    break;
                }
            }
            if (sum == len) {
                Hashstruct hs = new Hashstruct(Text, i, len);
//System.out.println(hs.hashvalue);
                Hashtable.add(hs);
            }
        }
        return Hashtable;
    }

    public int searchhashvalue(int hashvalue) {
        for (int i = 0; i < Hashtable.size(); i++) {
            if (Hashtable.get(i).hashvalue == hashvalue) {
                return Hashtable.get(i).getposition();
            }
        }
        return -1;
    }
}

class Hashstruct {

    int hashvalue;
    int p;
    int len;
    StringBuffer Text = new StringBuffer();

    Hashstruct(StringBuffer Text, int p, int l) {
        this.p = p;
        this.len = l;
        this.Text = Text;

        int h = 0;
        for (int i = p; i < p + l; i++) {
            h = h * 15 + getask(Text.charAt(i));
        }
        hashvalue = h % 19127;
    }

    public int getposition() {
        return p;
    }

    public int getlen() {
        return len;
    }

    public int gethashvalue() {
        return hashvalue;
    }

    public int getask(char c)//得到一个字符的ask值
    {
        if ((c >= 'a') && (c <= 'z')) {
            return ((int) c - 97);
        } else {
            switch (c) {
                case '_':
                    return 27;
                case ',':
                    return 28;
                case '+':
                    return 29;
                case '*':
                    return 30;
                case '\'':
                    return 31;
                case '=':
                    return 32;
                case '!':
                    return 33;
                default:
                    return 100;
            }
        }
    }

    public String toString() {
        return "hash" + "(" + p + "," + len + "," + hashvalue + ")";
    }
}

class QMatch {

    int Lque;
    LinkedList<Match> matches = new LinkedList<Match>();

    QMatch(int Lque) {
        this.Lque = Lque;
    }

    public int getL() {
        return Lque;
    }
}

class Match {

    int m;
    int n;
    int l;

    Match(int m, int n, int l) {
        this.m = m;
        this.n = n;
        this.l = l;
    }

    public int getm() {
        return m;
    }

    public int getn() {
        return n;
    }

    public int getl() {
        return l;
    }

    public String toString() {
        return "Match(" + m + "," + n + "," + l + ")";
    }
}
